'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-09-29 10:46:40
LastEditTime: 2025-09-29 11:35:37
'''
'''
@Descripttion: 
@version: 
@encoding: utf-8
@Author: qiurongcan
Date: 2025-09-29 10:46:40
LastEditTime: 2025-09-29 11:35:33
'''


class Solution:

    MOD = 1_000_000_007
    def InversePairs(self, nums):

        _, count = self.merge_sort(nums)

        return count % self.MOD

    


    def merge_sort(self, arr):
        if len(arr) <= 1:

            return arr, 0
        
        mid = len(arr) // 2

        left, count_left = self.merge_sort(arr[:mid])
        right, count_right = self.merge_sort(arr[mid:])
        merged, count_merged = self.merge(left, right)

        total = (count_left + count_right + count_merged) % self.MOD
        return merged, total

    
    def merge(self, left, right):
        i = j = 0
        merged = []
        count = 0

        while i < len(left) and j < len(right):

            if left[i] <= right[j]:
                merged.append(left[i])
                i += 1
            
            else:
                merged.append(right[j])
                count += len(left) - i
                count = count % self.MOD
                j += 1
            
        merged.extend(left[i:])
        merged.extend(right[j:])

        return merged, count


